package algorithms.leaning.class15;

/**
 * 示例:
 * 输入: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
 * 输出: [1,1,2,3]
 * 解析:
 * 起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
 * 0 0 0
 * 0 0 0
 * 0 0 0
 * <p>
 * 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。
 * 1 0 0
 * 0 0 0   Number of islands = 1
 * 0 0 0
 * <p>
 * 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。
 * 1 1 0
 * 0 0 0   岛屿的数量为 1
 * 0 0 0
 * <p>
 * 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。
 * 1 1 0
 * 0 0 1   岛屿的数量为 2
 * 0 0 0
 * <p>
 * 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。
 * 1 1 0
 * 0 0 1   岛屿的数量为 3
 * 0 1 0
 * <p>
 * 拓展：
 * 你是否能在 O(k log mn) 的时间复杂度程度内完成每次的计算？
 * （k 表示 positions 的长度）
 * <p>
 * 扩展：假如matrix而给的positions很少怎么优化
 *
 * @author guichang
 * @date 2021/6/14
 */

public class Code3_并查集_岛问题扩展 {
}